package top.wanzc.java.basic.sort;

import java.util.Arrays;

/**
 * ��������
 * ���ڽ��������һ��
 * @author zhengchong.wan
 *
 */
public class QuickSortDemo {
	
	public static void main(String[] args) {
		int a[] = {49, 38, 65, 97, 76, 13, 27, 49, 0, 0, 0, 0, 0};
		// �ٶ�a�ĳ���Ϊ8
		sort(a, 0, 7);
		System.out.println(Arrays.toString(a));
	}
	
	private static void sort(int[] a, int low, int high) {
		if (low < high) {
			int pivotPos = partition(a, low, high);
			sort(a, low, pivotPos - 1);
			sort(a, pivotPos + 1, high);
		}
	}
	
	private static int partition(int a[], int low, int high) {
		int pivot = a[low]; // ��һ��Ԫ����Ϊ��׼
		while (low < high) {
			while (low < high && a[high] >= pivot) --high; // �ҵ�һ��С�ڻ�׼��
			a[low] = a[high];
			while (low < high && a[low] <= pivot) ++low; // �ҵ�һ�����ڻ�׼��
			a[high] = a[low];
		}
		a[low] = pivot; // ��׼Ԫ�ش������λ�ã����ʱ��low == high
		return low;
	}

}
